#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-08-24 10:51 上午
# @Author  : yangdy
# @File    : 2020-08-22.4.1559.二维网格图中探测环
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        for gi in grid:
            print(gi)
        if not grid:
            return False
        n = len(grid)
        m = len(grid[0])
        ss = [[True for i in range(m)] for j in range(n)]
        color = {}

        steps = [
            (0, 1), (1, 0), (0, -1), (-1, 0)
        ]

        def dfs(op, ox, oy, x, y):
            if (x, y) in color:
                c = color[(x, y)]
                return True
            color[(x, y)] = 1
            ss[x][y] = False
            # for index, pi in enumerate(steps):
            ii = (op + 1) % 4
            while True:
                xx, yy = x+steps[ii][0], y+steps[ii][1]
                if 0 <= xx < n and 0 <= yy < m and not (xx == ox and yy == oy):
                    if grid[xx][yy] == grid[x][y]:
                        if dfs(ii, x, y, xx, yy):
                            return True
                if ii == op:
                    break
                ii = (ii+1) % 4

            color[(x, y)] = 2
            return False

        for i in range(n):
            for j in range(m):
                if ss[i][j]:
                    color = {}
                    if dfs(0, -1, -1, i, j):
                        return True

        return False


questions = [
    ([["a", "a", "a", "a"], ["a", "b", "b", "a"], ["a", "b", "b", "a"], ["a", "a", "a", "a"]], ),
    ([["c", "c", "c", "a"], ["c", "d", "c", "c"], ["c", "c", "e", "c"], ["f", "c", "c", "c"]], ),
    ([["a", "b", "b"], ["b", "z", "b"], ["b", "b", "a"]], ),
    ([["f", "c", "b", "d", "f", "a", "e", "e", "a", "c", "e"],
      ["d", "f", "f", "c", "c", "a", "b", "b", "a", "c", "f"],
      ["e", "d", "d", "a", "d", "d", "d", "c", "f", "b", "e"],
      ["e", "a", "d", "d", "a", "e", "e", "a", "c", "f", "b"],
      ["d", "c", "f", "a", "b", "c", "c", "d", "e", "c", "b"],
      ["d", "a", "e", "d", "a", "a", "a", "e", "f", "a", "b"],
      ["d", "f", "e", "a", "f", "b", "c", "b", "d", "a", "e"],
      ["c", "f", "d", "c", "d", "a", "e", "e", "a", "a", "e"],
      ["f", "b", "c", "e", "e", "b", "e", "b", "a", "a", "a"],
      ["d", "d", "b", "c", "b", "f", "a", "c", "b", "c", "d"],
      ["e", "e", "c", "c", "e", "b", "e", "f", "b", "c", "d"]], ),
    ([["c", "c", "c", "a"], ["c", "d", "c", "c"], ["c", "c", "e", "c"], ["f", "c", "c", "c"]], )
]

work(questions, lambda q: Solution().containsCycle(q[0]))
